Position FindLeaf(BTreeHead btree, ElemSet key) {
    /* 找到应该包含或可以插入key的叶结点 */
    /* 注意：此处默认btree不为空 */
    Position p;
    int i;

    p = btree->root; /* 从根结点开始查找 */
    while (p->leaf == false) { /* 循环直到找到叶结点 */
        for (i = 0; i < p->num_keys; i++) {
            if (key <= p->data[i]->key) {
                break; /* 找到结点中第一个不小于key的关键码 */
            }
        }
        if (i < p->num_keys) {
            p = p->children[i]; /* 继续在对应的子树中查找 */
        } else { /* 子树中所有关键码都比key小，则key不存在 */
            p = p->children[i - 1]; /* 沿最后一棵子树向下 */
        }
    }
    return p;
}

TElemSet SearchBTree(BTreeHead btree, ElemSet key) {
    /* 在B+树中查找关键码key，返回指向key所在记录的指针 */
    /* 注意：此处默认btree已经初始化 */
    TElemSet ret;
    Position p;
    int i;

    ret = NULL; /* 初始化返回值为空指针，表示未找到key */
    if (btree->root != NULL) { /* 对非空的B+树 */
        p = FindLeaf(btree, key); /* 找到应该包含key的叶结点 */
        for (i = 0; i < p->num_keys; i++) { /*顺序扫描查找关键码 */
            if (key == p->data[i]->key) {
                break;
            }
        }
        if (i < p->num_keys) { /* 找到了key */
            ret = p->data[i]; /* 返回以key为关键码的记录的指针 */
        }
        /* 否则 ret 是 NULL */
    }
    return ret;
}